package 剑指offer;

import 抽象数据类型.TreeNode;

import java.util.*;

import static 树.构造树.buildTree;

/**
 * @description:
 * @author: ywk
 * @date: 2020-10-18
 */
public class ThreeOrderTraverse {
    public static void main(String[] args) {
        TreeNode treeNode = buildTree(new int[]{1, 2, 3, 4, 5, 6, 7});
        System.out.println(threeOrders(treeNode));
//        System.out.println(levelOrder(treeNode));
//        System.out.println(preOrder(treeNode));
//        System.out.println(levelOrder(treeNode));


    }


    public static int[][] threeOrders(TreeNode root) {
        //通过后序遍历
        Stack<TreeNode> stack = new Stack<>();
        ArrayList<Integer> preList = new ArrayList<>();
        ArrayList<Integer> midList = new ArrayList<>();
        ArrayList<Integer> backList = new ArrayList<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                preList.add((Integer) root.val);
                root = root.left;
            }
            midList.add((Integer) stack.peek().val);
            while (!stack.isEmpty() && (stack.peek().right == root)) {
                root = stack.pop();
                backList.add((Integer) root.val);
            }
            if (!stack.isEmpty()) {
                midList.add((Integer) stack.peek().val);
                root = stack.peek().right;
            } else {
                int[][] arr = new int[3][preList.size()];
                System.out.println(preList);
                System.out.println(midList);
                System.out.println(backList);
                copyToArr(arr[0], preList);
                copyToArr(arr[1], midList);
                copyToArr(arr[2], backList);
                return arr;

            }
        }
        return null;
    }

    public static ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            ArrayList<Integer> temp = new ArrayList<Integer>();
            while (--size >= 0) {
                TreeNode remove = queue.remove();
                temp.add((Integer) remove.val);
                if (remove.left != null) {
                    queue.add(remove.left);
                }
                if (remove.right != null) {
                    queue.add(remove.right);
                }
            }
            list.add(temp);
        }
        return list;
    }

    public static List<Integer> backOrder(TreeNode root) {
        //通过后序遍历
        Stack<TreeNode> stack = new Stack<>();
        ArrayList<Integer> backList = new ArrayList<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            while (!stack.isEmpty() && (root == null || stack.peek().right != null && stack.peek().right == root)) {
                root = stack.pop();
                backList.add((Integer) root.val);
            }
            if (!stack.isEmpty()) {
                root = stack.peek().right;
            } else {

                return backList;
            }
        }
        return null;
    }

    public static List<Integer> preOrder(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        LinkedList<Integer> list = new LinkedList<>();
        while (true) {
            while (root != null) {
                stack.add(root);
                list.add((Integer) root.val);
                root = root.left;

            }
            root = stack.pop().right;

            if (stack.isEmpty() && root == null) {
                break;
            }

        }
        return list;
    }

    public static List<Integer> midOrder(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        LinkedList<Integer> list = new LinkedList<>();
        while (true) {
            while (root != null) {
                stack.add(root);
                root = root.left;

            }
            list.add((Integer) stack.peek().val);
            root = stack.pop().right;

            if (stack.isEmpty() && root == null) {
                break;
            }

        }
        return list;
    }

    public static void copyToArr(int[] arr, List<Integer> temp) {
        for (int i = 0; i < arr.length; i++) {
            arr[i] = temp.get(i);
        }
    }
}
